1. Field of the Invention
The present invention generally relates to virtual storage mechanisms for data processing systems and, more particularly, to an address translation mechanism which predicts page-crossings and translates page-addresses ahead of time.
2. Description of the Prior Art
Virtual storage organization and management for data processing systems are described, for example, by Harvey M. Deitel in An Introduction to Operating Systems, Addison-Wesley (1984), by Harold Lorin and Harvey M. Deitel in Operating Systems, Addison-Wesley (1981), and by Harold S. Stone in High-Performance Computer Architecture, Addison-Wesley (1987). In a virtual storage system, paging is a relocation and address-to-physical-location binding mechanism providing the user of the system with what appears to be a considerably larger memory space than is really available. The key feature of the virtual storage concept is disassociating the addresses referenced in a running process from the addresses available in main storage. The addresses referenced by the running process are called virtual addresses, while the addresses available in main storage are called real addresses. The virtual addresses must be mapped into real addresses as the process executes, and that is the function of the dynamic address translation (DAT) mechanism. One such mechanism employs a directory look aside table (DLAT), sometimes referred to as a translation lookaside buffer (TLB), which stores recent virtual address translations. For virtual addresses stored in the DLAT, the translation process requires only a single or, at most, a couple of machine cycles. For addresses not stored in the DLAT, the DAT process may take from fifteen to sixty cycles or more.
Translations from the virtual address to the real address must be made to find where the addressed instruction or data is in main memory. This is typically done on a page basis. In fact, the translations stored in the DLAT are actually only page translations, and the last bits of an address are the location in that page, so only the page address must be translated. Often, the addresses are in a specific order as in scientific computing where the addresses are at specific increments in memory. These increments are called a "stride". If all addresses are in incremental order, the stride is one, but if every other address is used, the stride is two, and so forth. This permits easy prediction of future addresses. In scientific or vector computing, an instruction specifies a starting address, the stride and number of operands in the instruction. This allows the address generation to increment the earlier translated address by the stride to obtain the next address thereby avoiding the overhead of address translation within a page. However, whenever a page-crossing is encountered, the next address must go to the DLAT or buffer control element (BCE) to translate a virtual page-address to a real page-address as before. Thus, there is the potential on a page-crossing for a DLAT "miss" which will cause a delay of thirty cycles or more.